package com.ljx.List;

import com.ljx.Dynamic.ListNode;

import java.util.List;

/**
 * @author 李加喜
 * @Package com.ljx.List
 * @date 2021-11-17 22:19
 */
// 反转链表
public class FuanZhuan {
    /**
     * 用于记录后续节点的
     */
    public static void main(String[] args) {
        System.out.println("实现操作");
    }
    public ListNode reverseList(ListNode head) {
        //
        if (head==null || head.next == null){ return head;}
        ListNode last=reverseList(head.next);
        // 然1 2 相互指向
        head.next.next=head;
        head.next=null;
        return last;
    }
    ListNode success=null;
    /**
     *  反转前n个节点
     */
    public ListNode reverseListN(ListNode head,int n) {
        if (n==1){
            // 记录第n+1个节点
            success=head.next;
            return head;
        }
        // 反转前n-1个节点
        ListNode lastNode=reverseListN(head.next,n-1);
        head.next.next=head;
        head.next=success;
        return lastNode;
    }
    /**
     *  反转前m-n个节点
     */
    public ListNode reverseBetween(ListNode head,int m,int n) {
        if (m==1){
            // 就是计算前n个节点
            return reverseListN(head,n);
        }
        // 反转前n-1个节点
        head.next=reverseBetween(head.next,m-1,n-1);
        return head;
    }
}
